package gold.contest;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC6115 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        int factor = 1000000007;

        public int idealArrays(int n, int maxValue) {
            long ans = 0;
            long[][] dp = new long[2][maxValue + 1];
            for (int i = 1; i <= maxValue; i++) dp[0][i] = 1;

            for (int i = 1; i < n; i++) {
                for (int j = 1; j <= maxValue; j++) {
                    dp[i % 2][j] = 0;// 以 j 开头，长度为 i + 1 的序列枚举数量
                    for (int k = 1; j * k <= maxValue; k++) {
                        dp[i % 2][j] = (dp[i % 2][j] + dp[(i - 1) % 2][j * k]) % factor;
                    }
                }
            }

            for (int j = 1; j <= maxValue; j++) {
                ans = (ans + dp[(n - 1) % 2][j]) % factor;
            }

            return (int) (ans % factor);
        }
    }


    class Solution_DFS_Not_Count {

        Map<String, Long> memo = new HashMap<>();
        int factor = 1000000007;

        public int idealArrays(int n, int maxValue) {
            long ans = 0;
            for (int i = 1; i <= maxValue; i++) {
                long dfsNext = dfs(i, n - 1, maxValue);
                ans = (ans + dfsNext) % factor;
            }

            return (int) (ans % factor);
        }

        public long dfs(int currentStartNum, int n, int maxValue) {
            if (n <= 0) return 1;
            if (currentStartNum > maxValue) return 0;
            String key = currentStartNum + "_" + n;
            if (memo.containsKey(key)) return memo.get(key);
            long curAns = 0;

            for (int i = 1; currentStartNum * i <= maxValue; i++) {
                long dfsNext = dfs(currentStartNum * i, n - 1, maxValue);
                curAns = (curAns + dfsNext) % factor;
            }

            memo.put(key, curAns);
            return curAns;
        }
    }

    public void run() {
        System.out.println(new Solution().idealArrays(5878, 2900));
        System.out.println(new Solution().idealArrays(2, 5));
        System.out.println(new Solution().idealArrays(5, 3));
    }

    public static void main(String[] args) throws Exception {
        LC6115 an = new LC6115();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
